๋ฌธ์
์ฐจ์ธ๋ ์๋์ธ ํ๋๋ ๊ฐ์๋ ๊ณ ๋ญ์ง์์ ์ ๊ธฐ๋ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๊ธฐ๋ก ํ์๋ค. ๋์ฝ์ ์ฐ์ง ์๊ณ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๋ ค๋ฉด ๋ฐฐ์ถ๋ฅผ ํด์ถฉ์ผ๋ก๋ถํฐ ๋ณดํธํ๋ ๊ฒ์ด ์ค์ํ๊ธฐ ๋๋ฌธ์, ํ๋๋ ํด์ถฉ ๋ฐฉ์ง์ ํจ๊ณผ์ ์ธ ๋ฐฐ์ถํฐ์ง๋ ์ด๋ฅผ ๊ตฌ์ ํ๊ธฐ๋ก ๊ฒฐ์ฌํ๋ค. ์ด ์ง๋ ์ด๋ ๋ฐฐ์ถ๊ทผ์ฒ์ ์์ํ๋ฉฐ ํด์ถฉ์ ์ก์ ๋จน์์ผ๋ก์จ ๋ฐฐ์ถ๋ฅผ ๋ณดํธํ๋ค. ํนํ, ์ด๋ค ๋ฐฐ์ถ์ ๋ฐฐ์ถํฐ์ง๋ ์ด๊ฐ ํ ๋ง๋ฆฌ๋ผ๋ ์ด๊ณ ์์ผ๋ฉด ์ด ์ง๋ ์ด๋ ์ธ์ ํ ๋ค๋ฅธ ๋ฐฐ์ถ๋ก ์ด๋ํ ์ ์์ด, ๊ทธ ๋ฐฐ์ถ๋ค ์ญ์ ํด์ถฉ์ผ๋ก๋ถํฐ ๋ณดํธ๋ฐ์ ์ ์๋ค. ํ ๋ฐฐ์ถ์ ์ํ์ข์ฐ ๋ค ๋ฐฉํฅ์ ๋ค๋ฅธ ๋ฐฐ์ถ๊ฐ ์์นํ ๊ฒฝ์ฐ์ ์๋ก ์ธ์ ํด์๋ ๊ฒ์ด๋ค.
ํ๋๊ฐ ๋ฐฐ์ถ๋ฅผ ์ฌ๋ฐฐํ๋ ๋ ์ ๊ณ ๋ฅด์ง ๋ชปํด์ ๋ฐฐ์ถ๋ฅผ ๊ตฐ๋ฐ๊ตฐ๋ฐ ์ฌ์ด ๋์๋ค. ๋ฐฐ์ถ๋ค์ด ๋ชจ์ฌ์๋ ๊ณณ์๋ ๋ฐฐ์ถํฐ์ง๋ ์ด๊ฐ ํ ๋ง๋ฆฌ๋ง ์์ผ๋ฉด ๋๋ฏ๋ก ์๋ก ์ธ์ ํด์๋ ๋ฐฐ์ถ๋ค์ด ๋ช ๊ตฐ๋ฐ์ ํผ์ ธ์๋์ง ์กฐ์ฌํ๋ฉด ์ด ๋ช ๋ง๋ฆฌ์ ์ง๋ ์ด๊ฐ ํ์ํ์ง ์ ์ ์๋ค. ์๋ฅผ ๋ค์ด ๋ฐฐ์ถ๋ฐญ์ด ์๋์ ๊ฐ์ด ๊ตฌ์ฑ๋์ด ์์ผ๋ฉด ์ต์ 5๋ง๋ฆฌ์ ๋ฐฐ์ถํฐ์ง๋ ์ด๊ฐ ํ์ํ๋ค. 0์ ๋ฐฐ์ถ๊ฐ ์ฌ์ด์ ธ ์์ง ์์ ๋ ์ด๊ณ , 1์ ๋ฐฐ์ถ๊ฐ ์ฌ์ด์ ธ ์๋ ๋ ์ ๋ํ๋ธ๋ค.
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
์ ๋ ฅ
- ์ฒซ ์ค์๋ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ทธ ๋ค์ ์ค๋ถํฐ ๊ฐ๊ฐ์ ํ ์คํธ ์ผ์ด์ค์ ๋ํด ์ฒซ์งธ ์ค์๋ ๋ฐฐ์ถ๋ฅผ ์ฌ์ ๋ฐฐ์ถ๋ฐญ์ ๊ฐ๋ก๊ธธ์ด M(1 โค M โค 50)๊ณผ ์ธ๋ก๊ธธ์ด N(1 โค N โค 50), ๊ทธ๋ฆฌ๊ณ ๋ฐฐ์ถ๊ฐ ์ฌ์ด์ ธ ์๋ ์์น์ ๊ฐ์ K(1 โค K โค 2500)์ด ์ฃผ์ด์ง๋ค. ๊ทธ ๋ค์ K์ค์๋ ๋ฐฐ์ถ์ ์์น X(0 โค X โค M-1), Y(0 โค Y โค N-1)๊ฐ ์ฃผ์ด์ง๋ค. ๋ ๋ฐฐ์ถ์ ์์น๊ฐ ๊ฐ์ ๊ฒฝ์ฐ๋ ์๋ค.
์ถ๋ ฅ
- ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ๋ํด ํ์ํ ์ต์์ ๋ฐฐ์ถํฐ์ง๋ ์ด ๋ง๋ฆฌ ์๋ฅผ ์ถ๋ ฅํ๋ค.
๐ Logic
class Pair {
private int first;
private int second;
Pair(int x, int y) {
this.first = x;
this.second = y;
}
public int getF() {
return first;
}
public int getS() {
return second;
}
}
Pair์ ๊ตฌํ์ ์ํด ์์ ๊ฐ์ class ๋ฅผ ์์ฑํ๋ค.
for (int a = 0; a < worm.size(); a++) {
int vF = worm.get(a).getF();
int vS = worm.get(a).getS();
if (visited[vF][vS] == 0) {
Queue<Pair> q = new LinkedList<>();
q.offer(worm.get(a));
visited[vF][vS] = 1;
while (!q.isEmpty()) {
Pair cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.getF() + x_ary[i], ny = cur.getS() + y_ary[i];
if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
if (visited[nx][ny] == 0 && map[nx][ny] == 1) {
visited[nx][ny] = 1;
q.offer(new Pair(nx, ny));
}
}
}
}
worms++;
}
}
- ๋ฐฐ์ถ์ ์์น ๋ฐ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ์ฌ์ฉํด ๋ฐฐ์ถํฐ์ง๋ ์ด๊ฐ ์ด๋ํ ์ ์๋ ๋ฐฐ์ถ์ ์์น๋ฅผ
Queue์DFS๋ฐฉ์์ผ๋ก ์ถ๊ฐํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int[] x_ary = {0, 0, -1, 1};
int[] y_ary = {-1, 1, 0, 0};
int[][] map = null;
int[][] visited = null;
visited = new int[50][50];
while (T > 0) {
int M = sc.nextInt();
int N = sc.nextInt();
int K = sc.nextInt();
int worms = 0;
map = new int[M][N];
ArrayList<Pair> worm = new ArrayList<>();
for (int[] tmp : visited)
Arrays.fill(tmp, 0);
for (int i = 0; i < K; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
map[x][y] = 1;
worm.add(new Pair(x, y));
}
for (int a = 0; a < worm.size(); a++) {
int vF = worm.get(a).getF();
int vS = worm.get(a).getS();
if (visited[vF][vS] == 0) {
Queue<Pair> q = new LinkedList<>();
q.offer(worm.get(a));
visited[vF][vS] = 1;
while (!q.isEmpty()) {
Pair cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.getF() + x_ary[i], ny = cur.getS() + y_ary[i];
if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
if (visited[nx][ny] == 0 && map[nx][ny] == 1) {
visited[nx][ny] = 1;
q.offer(new Pair(nx, ny));
}
}
}
}
worms++;
}
}
System.out.println(worms);
T -= 1;
}
sc.close();
}
}
class Pair {
private int first;
private int second;
Pair(int x, int y) {
this.first = x;
this.second = y;
}
public int getF() {
return first;
}
public int getS() {
return second;
}
}
โ๏ธ Review
c++๋ก ํ์๋ ๋ฌธ์ ๋ฅผjava๋ก ๋ณํํ์ฌ ๋ค์ ํ์ด๋ณธ ๋ฌธ์ - ๋
ผ๋ฆฌ ์์ฒด๋ ๊ธฐ๋ณธ์ ์ธ DFS๋ฅผ ์ฌ์ฉํ ๋ฌธ์ ์ฌ์
java๋ฌธ๋ฒ์ ์ค๋๋ง์ ๋ค์ ์จ๋ณธ ๋ฌธ์ ์๋ค.